1. Field of the Invention
The present invention relates generally to error correction devices and particularly to error correction devices successively providing error correction for a code in each direction for a data block including a product code.
2. Description of the Background Art
In environments transmitting digital data, such as digital transmission systems, peripheral apparatuses for computers and the like, error correction codes are typically used to more reliably transmit digital data. In particular, in recent years an error correction code having a high correction capability is used as a digital data receiving and decoding side is enhanced in data processing capability.
A representative one of such error correction codes is a product code, which has two long-distance codes with large code length and redundancy.
FIG. 13 schematically shows a manner in which such a product code is added to digital data (information symbol).
With reference to FIG. 13, the product code is typically a combination of error correction codes provided in different directions, i.e., vertical and horizontal directions. More specifically, the product code is configured of a parity PO corresponding to an external code added to the information symbol in the vertical direction and a parity PI corresponding to an internal code added to the information symbol and parity PO in the horizontal direction.
Each error correction code is often a Reed-Solomon code (hereinafter referred to as an RS code) capable of byte-by-byte error correction. In the FIG. 13 example, the error correction code in the PO direction is an RS code having a code length n0(=208), an information length k0(=192) and a minimal distance d0(=17), and the error correction code in the PI direction is an RS code having a code length ni(=182) an information length ki(=172) and a minimal distance di(=11).
Theoretically, there are established relationships of dixe2x89xa72ti+1 and d0xe2x89xa72t0+1, wherein ti and to are each a number of errors that can be corrected.
If a receiving and decoding apparatus decodes or corrects errors of a data block including a product code with RS error correction codes added in two directions, error correction in each direction is typically repeated, again and again.
FIG. 14 is a block diagram simply showing a data transmission path in an error correction process of such a first conventional error correction device.
With reference to FIG. 14, digital data read for example from a DVD is transmitted on a data bus 51, provided in the form of a data block including a product code, as shown in FIG. 13, and it is thus stored temporarily in a buffer memory 52. Buffer memory 52 typically has a large capacity of no less than 4 Mbit to store a plurality of product-code blocks at one time. As such, a dynamic random access memory (DRAM), a synchronous dynamic random access memory (SDRAM) or the like is mainly used as buffer memory 52 as it has a large capacity, occupies a small area and is not costly.
Then the data stored in buffer memory 52 are successively read and an error correction circuit 53 provides error correction for the code in each direction. Correcting errors with a Reed-Solomon code typically follows the following 4-step procedure:
(1) Calculate a syndrome from received data;
(2) Obtains an error location polynomial and an error estimation polynomial from the syndrome;
(3) Obtain an error location from the error location polynomial; and
(4) Obtain an error count value from the error location polynomial, the error estimation polynomial and the error location, and corrects the obtained error count value.
If a Reed-Solomon code having a high correction capability is used to correct an error, Euclidean algorithm obtaining the greatest common divider of two polynomials may be applied as one technique of obtaining an error location polynomial and an error estimation polynomial from a syndrome in step (2).
FIG. 15 is a schematic block diagram showing a configuration of error correction circuit 53. Error correction circuit 53 is configured of a syndrome calculation circuit 54 provided for calculating a syndrome from data input, a Euclidean execution circuit 55 provided for obtaining an error location polynomial and an error estimation polynomial from a syndrome, a Chien search execution circuit 56 obtaining an error location and an error count value from an error location polynomial and an error estimation polynomial, and a correction circuit 57 providing a correction based on an error location and an error count value.
In the FIG. 13 product-code block, for example, the horizontal, PI-system data is subjected to a calculation of a syndrome, a calculation of an error location polynomial and an error count value polynomial by means of a Euclidean method, and a calculation of an error location and an error value by means of a Chien search method, and on buffer memory 52 an error is corrected.
Then, the vertical, PO-system data is subjected to a calculation of a syndrome, a calculation of an error location polynomial and an error count value polynomial by means of a Euclidean method, and a calculation of an error location and an error value by means of a Chien search method, and on buffer memory 52 an error is corrected.
Such a process is repeated for each system to correct an error in an information symbol. If this error correction process is repeated more frequently, more errors can be corrected in general.
In the FIG. 14 example, a buffer memory 52 comprises, for instance, a dynamic random access memory (D)RAM). Horizontal, PI-system data stored in the buffer memory 52 can be accessed in burst and thus read rapidly. However, vertical, PO-system data are accessed randomly and thus read in a long period of time, disadvantageously resulting in a reduced correction rate.
To overcome this disadvantage, there is provided a second conventional error correction device having a configuration illustrated in FIG. 16, shown in a schematic block diagram.
As shown in FIG. 16, the second conventional error correction device has added thereto a storage element 58 formed of a static random access memory (SRAM) rapidly accessible for both of data in a vertical direction and data in a horizontal direction. In accessing horizontal, PI-system data stored in buffer memory 52, the data of a product code block are all written to storage element 58. More specifically, there is proposed that if the vertical, PO-system data is accessed, a product code block stored in storage element 58 is accessed to allow the vertical, PO-system data to also be accessed rapidly.
In the conventional example as shown in FIG. 16, however, storage element 58 corresponding to an SRAM is enormously increased in capacity, disadvantageously resulting in an increased circuit area and an increased power consumption.
The present invention contemplates an error correction device capable of rapid error correction while minimizing a storage element in capacity.
The present invention provides an error correction device including a first storage element, a first error correction operation circuit and a second error correction operation circuit.
The first storage element stores a product-code block having added thereto error correction codes provided in different directions. The first error correction operation circuit receives from the first storage element data in the product code block arranged in a first direction, and corrects an error in the first direction. The second error correction operation circuit receives from the first error correction circuit the data corrected by the first error correction circuit, and successively corrects an error in a second direction.
Thus the present invention can provide an error correction device capable of rapid error correction while minimizing circuit area and power consumption.